/**
 * 题目：矩阵区域和
 * 链接；https://leetcode.cn/problems/matrix-block-sum/description/
 **/

public class Test {
    public static void main(String[] args) {
        //
    }
}

/*class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        //非同等规模的，前缀和数组——多一行一列，方便边界处理（这也是一种处理技巧）
        int[][] dp = new int[m+1][n+1];
        //同等规模的，要返回的数组（矩阵）
        int[][] res = new int[m][n];

        //初始化这个前缀和数组
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1] ;
            }
        }

        //使用前缀和数组（填写要返回的数组）
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int x1 = Math.max(0, i - k)+1;
                int y1 = Math.max(0, j - k)+1;

                int x2 = Math.min(m - 1, i + k)+1;
                int y2 = Math.min(n - 1, j + k)+1;

                res[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];

            }
        }
        return res;
    }
}*/

//正确运行的代码：（注意，认真画个图，清晰一点，对边界的分析仔细一点，不要“想当然”）
class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        //创建一个前缀和数组（注意：多加一行一列，方便边界处理）
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
            }
        }

        //使用这个前缀和数组
        int[][] res = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int x1 = Math.max(0, i - k) + 1;
                int y1 = Math.max(0, j - k) + 1;

                int x2 = Math.min(m - 1, i + k) + 1;
                int y2 = Math.min(n - 1, j + k) + 1;

                res[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];

            }
        }
        return res;

    }
}